package heap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class MaxHeap {
    //保存元素的数组
    private List<Integer> arr;
    private int size;

    public MaxHeap(){
        this(10);
    }

    public MaxHeap(int capacity){
        this.arr = new ArrayList<>(capacity);
    }

    public MaxHeap(int[] num){
        //将数组建成堆时间复杂度是O(n)
        this.arr = new ArrayList<>();
        for (int i: num) {
            arr.add(i);
            size++;
        }
        for (int i = parent(size-1); i >=0 ; i--) {
            siftDown(i);
        }
    }

    public  int peekMax(){
        if(arr.isEmpty()){
            throw new NoSuchElementException("heap is empty, can not peek");
        }
        return arr.get(0);
    }

    //获取当前堆顶元素
    public int extractMax(){
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty!");
        }
        int ret = arr.get(0);
        arr.set(0,arr.get(size-1));
        arr.remove(size-1);
        size--;
        siftDown(0);
        return ret;
    }

    private void siftDown(int k) {
        while (leftChild(k)<size){
            int j = leftChild(k);
            if(j+1<size&&arr.get(j+1)>arr.get(j)){
                j = j+1;
            }
            if(arr.get(j)>arr.get(k)){
                swap(j,k);
                k = j;
            }else {
                break;
            }
        }
    }

    //获取当前元素的父元素的下标
    private int parent(int k) {
        if (k > 0) {
            return (k - 1) >> 1;
        }
        return -1;
    }

    //获取当前节点左子节点的编号
    private int leftChild(int k) {
        return (k << 1) + 1;
    }

    //获取当前右子树节点的编号
    private int rightChild(int k) {
        return leftChild(k)+1;
    }

    public boolean isEmpty(){
        return this.size==0;
    }

    public void add(int val) {
        //尾插
        this.arr.add(val);
        this.size++;
        //进行元素的上浮操作
        siftUp(size-1);
    }

    private void siftUp(int k) {
        if(k==0){
            return;
        }
        //存在父节点,且子节点的值比父节点大
        while (k>0&&arr.get(k)>arr.get(parent(k))){
            swap(k,parent(k));
            k = parent(k);
        }
    }

    private void swap(int i, int j) {
        int tmp = arr.get(i);
        arr.set(i,arr.get(j));
        arr.set(j,tmp);
    }

    @Override
    public String toString() {
        return arr.toString();
    }
}
